package getOffer.offer68_2;

/**
 * @Author: wjy
 * @Date: 2021/11/8 9:06
 */
public class Solution {

    public static void main(String[] args) {

        TreeNode treeNode1 = new TreeNode(7);
        TreeNode treeNode2 = new TreeNode(4);
        TreeNode treeNode3 = new TreeNode(2);
        treeNode3.left = treeNode1;
        treeNode3.right = treeNode2;
        TreeNode treeNode4 = new TreeNode(6);
        TreeNode treeNode5 = new TreeNode(5);
        treeNode5.left = treeNode4;
        treeNode5.right = treeNode3;
        TreeNode treeNode6 = new TreeNode(0);
        TreeNode treeNode7 = new TreeNode(8);
        TreeNode treeNode8 = new TreeNode(1);
        treeNode8.left = treeNode6;
        treeNode8.right = treeNode7;
        TreeNode treeNode9 = new TreeNode(3);
        treeNode9.left = treeNode5;
        treeNode9.right = treeNode8;

        Solution solution = new Solution();
        System.out.println(solution.lowestCommonAncestor(treeNode9, treeNode5, new TreeNode(67)).val);

    }

    /**
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if(left == null) {
            return right;
        }
        if(right == null) {
            return left;
        }
        return root;
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}